package tree.迭代bfs;

import po.TreeNode;

import java.util.*;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 在二叉树中增加一行623.java
 * @Description https://leetcode-cn.com/problems/add-one-row-to-tree/
 * @createTime 2021年06月23日 19:46:00
 */
public class 在二叉树中增加一行623 {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth==1) {
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        depth -= 1;
        Deque<TreeNode> tempDeque ;
        while (!deque.isEmpty()) {
            int size = deque.size();
            //记录对应行数的前一行
            tempDeque = new LinkedList<>(deque);
            depth--;
            //或者到达对应行数
            if (depth - 1 == 0) {
                for (int i = tempDeque.size(); i > 0; i--) {
                    TreeNode treeNode = tempDeque.remove();
                    TreeNode temp=treeNode.left;
                    TreeNode node = new TreeNode(val);
                    treeNode.left=node;
                    node.left=temp;
                    temp=treeNode.right;
                    TreeNode node1 = new TreeNode(val);
                    treeNode.right=node1;
                    node1.right=temp;
                }
            } else {
                for (int i = size; i > 0; i--) {
                    TreeNode treeNode = deque.poll();
                    if (treeNode == null) {
                        continue;
                    }
                    if (treeNode.left != null) {
                        deque.offer(treeNode.left);
                    }
                    if (treeNode.right != null) {
                        deque.offer(treeNode.right);
                    }
                }
            }

        }
        return root;
    }

}
